package com.caochenlei.tree.bst;

import java.util.LinkedList;
import java.util.Queue;

public class BinarySearchTree<Key extends Comparable<Key>, Value> {
    private class Node {    //结点类
        public Key key;     //存储键
        public Value value; //存储值
        public Node left;   //指向左子结点
        public Node right;  //指向右子结点

        public Node(Key key, Value value) {
            this.key = key;
            this.value = value;
        }

        @Override
        public String toString() {
            return "Node{" + "key=" + key + ", value=" + value + "}";
        }
    }

    private Node root;      //根结点
    private int N;          //结点数

    //获取当前树的结点数
    public int size() {
        return N;
    }

    //判断当前树是否为空
    public boolean isEmpty() {
        return N == 0;
    }

    //向当前树中添加结点
    public void put(Key key, Value value) {
        root = put(root, key, value);
    }

    //向指定树中添加结点
    private Node put(Node x, Key key, Value value) {
        //如果x子树为空，直接返回新结点
        if (x == null) {
            N++;
            return new Node(key, value);
        }
        //如果x子树不空，根据情况来插入
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = put(x.left, key, value);
        } else if (cmp > 0) {
            x.right = put(x.right, key, value);
        } else {
            x.value = value;
        }
        return x;
    }

    //在当前树中根据Key获取Value
    public Value get(Key key) {
        return get(root, key);
    }

    //在指定树中根据Key获取Value
    private Value get(Node x, Key key) {
        //如果x子树为空，直接返回null
        if (x == null) {
            return null;
        }
        //如果x子树不空，根据情况返回
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            return get(x.left, key);
        } else if (cmp > 0) {
            return get(x.right, key);
        } else {
            return x.value;
        }
    }

    //在当前树中获取最小的Key
    public Key min() {
        return min(root).key;
    }

    //在指定树中获取最小的结点
    private Node min(Node x) {
        if (x.left == null) {
            return x;
        }
        return min(x.left);
    }

    //在当前树中获取最大的Key
    public Key max() {
        return max(root).key;
    }

    //在指定树中获取最大的结点
    private Node max(Node x) {
        if (x.right == null) {
            return x;
        }
        return max(x.right);
    }

    //获取当前树最大深度
    public int maxDepth() {
        return maxDepth(root);
    }

    //获取指定树最大深度
    private int maxDepth(Node x) {
        if (x == null) {
            return 0;
        }
        // x结点的最大深度
        int max = 0;
        //左子树的最大深度
        int maxL = 0;
        //右子树的最大深度
        int maxR = 0;
        //计算x结点左子树的最大深度
        if (x.left != null) {
            maxL = maxDepth(x.left);
        }
        //计算x结点右子树的最大深度
        if (x.right != null) {
            maxR = maxDepth(x.right);
        }
        //比较左子树和右子树最大深度
        max = maxL > maxR ? maxL + 1 : maxR + 1;
        return max;
    }

    //删除当前树中最小的结点
    public void deleteMin() {
        root = deleteMin(root);
    }

    //删除指定树中最小的结点
    private Node deleteMin(Node x) {
        if (x.left == null) {
            N--;
            return x.right;
        }
        x.left = deleteMin(x.left);
        return x;
    }

    //删除当前树中最大的结点
    public void deleteMax() {
        root = deleteMax(root);
    }

    //删除指定树中最大的结点
    private Node deleteMax(Node x) {
        if (x.right == null) {
            N--;
            return x.left;
        }
        x.right = deleteMin(x.right);
        return x;
    }

    //删除当前树中指定Key对应的结点
    public void delete(Key key) {
        root = delete(root, key);
    }

    //删除指定树中指定Key对应的结点
    private Node delete(Node x, Key key) {
        //如果x子树为空，直接返回null
        if (x == null) {
            return null;
        }
        //如果x子树不空，根据情况删除
        int cmp = key.compareTo(x.key);
        if (cmp < 0) {
            x.left = delete(x.left, key);
        } else if (cmp > 0) {
            x.right = delete(x.right, key);
        } else {
            //删除左叶子结点或有一个孩子的情况
            if (x.left == null) {
                N--;
                return x.right;
            }
            //删除右叶子结点或有一个孩子的情况
            else if (x.right == null) {
                N--;
                return x.left;
            }
            //删除非叶子结点
            else {
                Node t = x;
                x = min(t.right);
                x.right = deleteMin(t.right);
                x.left = t.left;
            }
        }
        return x;
    }

    //前序遍历当前树
    public void preErgodic() {
        preErgodic(root);
    }

    //前序遍历指定树
    private void preErgodic(Node x) {
        if (x == null) {
            return;
        }
        //输出根结点
        System.out.println(x);
        //遍历左子树
        if (x.left != null) {
            preErgodic(x.left);
        }
        //遍历右子树
        if (x.right != null) {
            preErgodic(x.right);
        }
    }

    //中序遍历当前树
    public void midErgodic() {
        midErgodic(root);
    }

    //中序遍历指定树
    private void midErgodic(Node x) {
        if (x == null) {
            return;
        }
        //遍历左子树
        if (x.left != null) {
            midErgodic(x.left);
        }
        //输出根结点
        System.out.println(x);
        //遍历右子树
        if (x.right != null) {
            midErgodic(x.right);
        }
    }

    //后序遍历当前树
    public void postErgodic() {
        postErgodic(root);
    }

    //后序遍历指定树
    private void postErgodic(Node x) {
        if (x == null) {
            return;
        }
        //遍历左子树
        if (x.left != null) {
            postErgodic(x.left);
        }
        //遍历右子树
        if (x.right != null) {
            postErgodic(x.right);
        }
        //输出根结点
        System.out.println(x);
    }

    //层序遍历当前树
    public void layerErgodic() {
        layerErgodic(root);
    }

    //层序遍历指定树
    private void layerErgodic(Node x) {
        //创建一个队列
        Queue<Node> nodes = new LinkedList<>();
        //加入指定节点
        nodes.offer(x);
        //循环弹出遍历
        while (!nodes.isEmpty()) {
            //从队列中弹出一个结点，输出当前结点的信息
            Node n = nodes.poll();
            System.out.println(n);
            //判断当前结点还有没有左子结点，如果有，则放入到nodes中
            if (n.left != null) {
                nodes.offer(n.left);
            }
            //判断当前结点还有没有右子结点，如果有，则放入到nodes中
            if (n.right != null) {
                nodes.offer(n.right);
            }
        }
    }
}
